import java.util.ArrayList;
import java.util.List;

/**
 * @作者 zxy
 * @时间 2023-03-29 9:34
 * @说明 95. 不同的二叉搜索树 II
 * 给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案
 */
public class Solution {
    public static void main(String[] args) {
        List<TreeNode> treeNodes = generateTrees(5);
        System.out.println(treeNodes);
    }

    static List<TreeNode> list = new ArrayList();
    static int num = 0;

    public static List<TreeNode> generateTrees(int n) {
        num = n;
        for (int i = 1; i <= n; i++) {
            TreeNode treeNode = new TreeNode(i);
            int[] left = new int[i - 1];
            for (int j = 0; j < left.length; j++) {
                left[j] = j + 1;
            }
            int[] right = new int[n - i];
            for (int j = 0; j < right.length; j++) {
                right[j] = i + 1 + j;
            }
            createDefferenceTree(treeNode, treeNode, left, right);
//            list.add(treeNode);
        }
        return list;
    }

    public static TreeNode cloneTree(TreeNode root) {
        // write your code here
        TreeNode clone = new TreeNode(0);
        if (root != null) {
            TreeNode temp = new TreeNode(0);
            clone.val = root.val;
            clone.left = cloneTree(root.left);
            clone.right = cloneTree(root.right);
        } else clone = null;
        return clone;
    }

    public static int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + countNodes(root.left) + countNodes(root.right);
    }


    public static void createDefferenceTree(TreeNode head, TreeNode treeNode, int[] left, int[] right) {
        if (left.length == 0 && right.length == 0) {
            if (countNodes(head) == num) {
                list.add(cloneTree(head));
            }
        }
        for (int i = 0; i < left.length; i++) {
            TreeNode treeNode1 = new TreeNode(left[i]);
            treeNode.left = treeNode1;
            int[] left1 = new int[i];
            for (int j = 0; j < left1.length; j++) {
                left1[j] = left[j];
            }
            int[] right1 = new int[left.length - left1.length - 1];
            for (int j = 0; j < right1.length; j++) {
                right1[j] = left[i + 1 + j];
            }
            createDefferenceTree(head, treeNode1, left1, right1);
        }
        for (int i = 0; i < right.length; i++) {
            TreeNode treeNode1 = new TreeNode(right[i]);
            treeNode.right = treeNode1;
            int[] left1 = new int[i];
            for (int j = 0; j < left1.length; j++) {
                left1[j] = right[j];
            }
            int[] right1 = new int[right.length - left1.length - 1];
            for (int j = 0; j < right1.length; j++) {
                right1[j] = right[i + 1 + j];
            }
            createDefferenceTree(head, treeNode1, left1, right1);
        }
    }
}
